package leetcode.L230;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        //使用中序遍历
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            k--;
            if (k == 0) {
                break;
            }
            root=root.right;
        }
        return root.val;
    }
}